package interview;

import java.util.LinkedList;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
public class interview_04_03 {
    public ListNode[] listOfDepth(TreeNode tree) {
        LinkedList<TreeNode> queue=new LinkedList<>();
        LinkedList<TreeNode> nextqueue=new LinkedList<>();
        LinkedList<ListNode> result=new LinkedList<>();
        if(tree==null) return new ListNode[0];
        queue.add(tree);
        while(!queue.isEmpty()){
            ListNode head=new ListNode(0);
            ListNode p=head;
            while(!queue.isEmpty()){
                TreeNode node=queue.removeFirst();
                p.next=new ListNode(node.val);
                p=p.next;
                if(node.left!=null)nextqueue.add(node.left);
                if(node.right!=null) nextqueue.add(node.right);
            }
            while(!nextqueue.isEmpty()){
                queue.add(nextqueue.removeFirst());
            }
            result.add(head.next);
        }
        int size= result.size();
        ListNode[] list=new ListNode[size];
        for(int i=0;i<size;++i){
            list[i]=result.removeFirst();
        }
        return list;
    }
}
